package com.leetcode.code;

import java.util.Arrays;

/**
 * Description:
 *
 * @author zkingcobra
 * Date: 2020/6/4 10:35 下午
 */
public class LeetCode0238Java {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(Arrays.toString(solution.productExceptSelf2(new int[] { 2, 4, 1, 3, 5 })));
    }

    static private class Solution {
        /**
         * 方法一：左右乘机列表
         *
         * @author zkingcobra 比官方的优化了 少用一个for循环处理后缀
         */
        public int[] productExceptSelf(int[] nums) {
            int[] result = new int[nums.length];
            int[] prefixResult = new int[nums.length];
            int[] suffixResult = new int[nums.length];

            prefixResult[0] = 1;

            suffixResult[nums.length - 1] = 1;

            for (int i = 1; i < nums.length; i++) {
                prefixResult[i] = nums[i - 1] * prefixResult[i - 1];

                suffixResult[nums.length - 1 - i] = nums[nums.length - i] * suffixResult[nums.length - i];
            }

            for (int i = 0; i < nums.length; i++) {
                result[i] = suffixResult[i] * prefixResult[i];
            }

            return result;
        }

        /**
         * 方法二：左右乘机列表进阶
         *
         * @author zkingcobra 优化空间复杂度
         */
        public int[] productExceptSelf2(int[] nums) {

            int[] prefixResult = new int[nums.length];

            int[] suffixResult = new int[nums.length];

            prefixResult[0] = 1;

            suffixResult[nums.length - 1] = 1;

            for (int i = 1; i < nums.length; i++) {
                prefixResult[i] = nums[i - 1] * prefixResult[i - 1];

                suffixResult[nums.length - 1 - i] = nums[nums.length - i] * suffixResult[nums.length - i];
            }

            for (int i = 0; i < nums.length; i++) {
                prefixResult[i] = suffixResult[i] * prefixResult[i];
            }

            return prefixResult;
        }

        /**
         * 超出时间限制
         * 方法：暴力法
         */
        public int[] productExceptSelf3(int[] nums) {

            int[] result = new int[nums.length];

            for (int i = 0; i < nums.length; i++) {
                int[] tempNums = nums.clone();

                tempNums[i] = 1;

                int temp = 1;

                for (int j = 0; j < nums.length; j++) {
                    temp *= tempNums[j];
                }

                result[i] = temp;
            }
            return result;
        }
    }
}
